// 栈的相关算法
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/// @brief 交换两个字符值
/// @param a 第一个字符指针
/// @param b 第二个字符指针
void swap(char *a, char *b)
{
	char temp = *a;
	*a = *b;
	*b = temp;
}

/// @brief 列出一个字符串序列按顺序入栈，所有出栈的情况
/// @param str 入栈的字符串序列
/// @param start 要列举的起始索引
/// @param end 要列举的终止索引
void stackAllRange(char str[], int start, int end)
{
	if (start == end)
	{
		// 三个for循环检验全排列中不合理的出栈序列
		// 进行排列组合后的str即为出栈序列，其中的下标可以看作出栈顺序，那么如果出现i < j < k并且str[i] > str [k] > str[j]的情况，就进行排除，因为这种情况是不可能的
		// str中的每个字符对应的ASCII码是有序的，即能够保证原始字符串中str[n - 1] < str[n]，因此可以用str中字符的ASCII码比较出原始字符串中的下标的先后，即入栈顺序
		// 所以在全排列的基础上去除掉上述的情况即可
		int i, j, k;
		for (i = 0; i <= end - 2; i++)
		{
			for (j = i + 1; j <= end - 1; j++)
			{
				for (k = j + 1; k <= end; k++)
				{
					if (str[i] > str[k] && str[i] > str[j] && str[k] > str[j])
					{
						return;
					}
				}
			}
		}
		printf("%s\n", str);
		return;
	}
	int i;
	for (i = start; i <= end; i++)
	{
		swap(&str[i], &str[start]);
		stackAllRange(str, start + 1, end);
		swap(&str[i], &str[start]);
	}
}

/// 1. 计算后缀表达式的值：从左到右遍历表达式，对于遍历的每个字符，有下列情况：
/// (1) 如果是操作数则入栈
/// (2) 遇到操作符则栈顶两个数出栈然后通过操作符计算后入栈（注意次序，弹出的第一个数位于操作符后，第二个数在操作符前）
/// 2. 中缀表达式转后缀表达式：从左到右遍历表达式，对于遍历的每个字符，有下列情况：
/// (1) 如果是操作数则直接放入结果
/// (2) 如果不是数字，那就是操作符（加减乘除）与括号，则分为下面情况讨论：
///  1) 栈为空时，直接压入当前符号
///  2) 当前符号为+或者-，则依次弹出栈顶元素并放入结果，直到栈为空或者栈顶为左括号为止，再把当前元素压入栈
///  3) 当前符号为*或者/，如果栈不为空且栈顶也是*或者/，就依次弹出栈内元素并放入结果，直到栈为空或者栈顶元素不再是*或者/为止，再把当前元素压入栈
///  4) 当前符号为(，则直接入栈
///  5) 当前符号为)，则依次弹出栈内符号并放入结果，直到遇到左括号为止，最后把左括号弹出但不放入结果
/// (3) 读取到表达式末尾则依次弹出全部栈内操作符并放入结果

/// @brief 判断当前字符是否是操作符
/// @param c 判断字符
/// @return 是否是操作符（加减乘除）
int isOperator(char c)
{
	if (c == '+' || c == '-' || c == '*' || c == '/')
	{
		return 1;
	}
	return 0;
}

/// @brief 计算简单表达式
/// @param a 第一个数
/// @param b 第二个数
/// @param c 操作符
/// @return 计算结果
double calculate(double a, double b, char c)
{
	if (c == '+')
	{
		return a + b;
	}
	if (c == '-')
	{
		return a - b;
	}
	if (c == '*')
	{
		return a * b;
	}
	if (c == '/')
	{
		return a / b;
	}
	return 0;
}

/// @brief 判断操作符的优先级
/// @param a 第一个操作符
/// @param b 第二个操作符
/// @return 第一个操作符优先级是否大于第二个操作符
int isPrior(char a, char b)
{
	if ((a == '*' || a == '/') && (b == '+' || b == '-'))
	{
		return 1;
	}
	return 0;
}

/// @brief 计算后缀表达式的值
/// @param expression 后缀表达式字符串
/// @return 表达式的值
double calculateSuffix(char expression[])
{
	// 分别为每次计算时的两个操作数和存放数字的栈
	double a, b, stack[100];
	// 分别为遍历字符串的下标和栈顶指针下标，栈顶指针总是指着栈顶元素所在位置
	int i, top = -1;
	// 遍历后缀表达式字符串
	for (i = 0; expression[i] != '\0'; i++)
	{
		// 遇到操作数则进栈
		if (!isOperator(expression[i]))
		{
			// 数字字符转数字，减去字符'0'即可
			stack[++top] = (double)(expression[i] - '0');
		}
		else
		{
			// 遇到操作符则弹出栈顶两个数计算再压入栈
			b = stack[top--];
			a = stack[top--];
			// 计算结果压入栈
			stack[++top] = calculate(a, b, expression[i]);
		}
	}
	// 最终栈里面只会剩下一个元素即为结果
	return stack[top];
}

/// @brief 中缀表达式转后缀表达式
/// @param expression 中缀表达式字符串
/// @return 转换后的后缀表达式
char *normalToSuffix(char expression[])
{
	// 分别表示遍历中缀表达式的下标、结果表达式的下标、表达式长度和栈顶指针下标，其中栈顶指针总是指向栈顶元素
	int i, j = 0, length = strlen(expression), top = -1;
	// 分别表示存放操作符的栈、结果表达式，字符串以'\0'结尾所以分配length + 1个空间
	char stack[100], *result = (char *)calloc(length + 1, sizeof(char));
	for (i = 0; i < length; i++)
	{
		// 如果是数字则直接放入结果
		if (!isOperator(expression[i]) && expression[i] != '(' && expression[i] != ')')
		{
			result[j++] = expression[i];
		}
		else
		{
			// 否则就是操作符与括号
			// 栈为空或者当前符号为左括号则直接压入
			if (top == -1 || expression[i] == '(')
			{
				stack[++top] = expression[i];
				continue;
			}
			// 当前符号为+或者-，则依次弹出栈顶元素并放入结果，直到栈为空或者栈顶为左括号时，再把当前元素压入栈
			if (expression[i] == '+' || expression[i] == '-')
			{
				while (top != -1 && stack[top] != '(')
				{
					result[j++] = stack[top--];
				}
				stack[++top] = expression[i];
				continue;
			}
			// 当前符号为*或者/，则只有栈顶也是*或者/时才能弹出并放入结果
			if (expression[i] == '*' || expression[i] == '/')
			{
				while (top != -1 && (stack[top] == '*' || stack[top] == '/'))
				{
					result[j++] = stack[top--];
				}
				stack[++top] = expression[i];
				continue;
			}
			// 当前符号为右括号，则依次弹出栈内符号并放入结果，直到遇到左括号为止，最后把左括号弹出但不放入结果
			if (expression[i] == ')')
			{
				while (stack[top] != '(')
				{
					result[j++] = stack[top--];
				}
				// 最后弹出左括号
				top--;
			}
		}
	}
	// 表达式读取完成，若栈仍不为空则依次弹出全部剩余操作符并放入结果
	while (top != -1)
	{
		result[j++] = stack[top--];
	}
	// 结束字符串
	result[j] = '\0';
	return result;
}

int main()
{
	char a[] = "2+(3*2+2*((5*2)+1))";
	char *s = normalToSuffix(a);
	printf("%s\n", s);
	printf("%f", calculateSuffix(s));
	return 0;
}